{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Additions to Make Valid String"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #greedy #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #贪心 #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: addMinimum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #构造有效字符串的最少插入数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串 <code>word</code> ，你可以向其中任何位置插入 \"a\"、\"b\" 或 \"c\" 任意次，返回使 <code>word</code> <strong>有效</strong> 需要插入的最少字母数。</p>\n",
    "\n",
    "<p>如果字符串可以由 \"abc\" 串联多次得到，则认为该字符串 <strong>有效</strong> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>word = \"b\"\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>在 \"b\" 之前插入 \"a\" ，在 \"b\" 之后插入 \"c\" 可以得到有效字符串 \"<strong>a</strong>b<strong>c</strong>\" 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>word = \"aaa\"\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>在每个 \"a\" 之后依次插入 \"b\" 和 \"c\" 可以得到有效字符串 \"a<strong>bc</strong>a<strong>bc</strong>a<strong>bc</strong>\" 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>word = \"abc\"\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>word 已经是有效字符串，不需要进行修改。 \n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= word.length &lt;= 50</code></li>\n",
    "\t<li><code>word</code> 仅由字母 \"a\"、\"b\" 和 \"c\" 组成。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-additions-to-make-valid-string](https://leetcode.cn/problems/minimum-additions-to-make-valid-string/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-additions-to-make-valid-string](https://leetcode.cn/problems/minimum-additions-to-make-valid-string/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"b\"', '\"aaa\"', '\"abc\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addMinimum(self, word: str) -> int:\n",
    "        # 贪心\n",
    "        ans, n = 1, len(word)\n",
    "        for i in range(1, n):\n",
    "            if word[i] <= word[i - 1]:\n",
    "                ans += 1\n",
    "        return ans * 3 - n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addMinimum(self, word: str) -> int:\n",
    "        index=0\n",
    "        n=len(word)\n",
    "        ls=[]\n",
    "        for i in range(1,n):\n",
    "            if ord(word[i])<=ord(word[i-1]):\n",
    "                ls.append(word[index:i])\n",
    "                index=i\n",
    "        ls.append(word[index:])\n",
    "        print(ls)\n",
    "        print(ord(\"a\"))\n",
    "        return 3*len(ls)-n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addMinimum(self, word: str) -> int:\n",
    "        part = [\"a\", \"b\", \"c\"]\n",
    "        list = []\n",
    "        count = 1\n",
    "        index = 0\n",
    "        first = True \n",
    "        res = 0  \n",
    "\n",
    "        for item in word:\n",
    "            if first:\n",
    "                first = False\n",
    "                index = part.index(item)\n",
    "                # continue\n",
    "            else:\n",
    "                if part.index(item) > index:\n",
    "                    count += 1\n",
    "                    index =  part.index(item)\n",
    "                else:\n",
    "                    # first = True\n",
    "                    # list.append(count)\n",
    "                    res += 3 - count\n",
    "                    index =  part.index(item)\n",
    "                    count = 1\n",
    "        # list.append(count) \n",
    "        res += 3 - count   \n",
    "        # print(list)\n",
    "        # res = 0\n",
    "        # for i in list:\n",
    "        #     res += 3 - i\n",
    "        # print(res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addMinimum(self, word: str) -> int:\n",
    "        t = 1 + sum(x >= y for x, y in pairwise(word))\n",
    "        return t * 3 - len(word)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addMinimum(self, word: str) -> int:\n",
    "        stack = []\n",
    "        res = 0\n",
    "        for token in word:\n",
    "            if stack:\n",
    "                if stack[-1]+token == 'ab':\n",
    "                    stack.append(token)\n",
    "                elif stack[-1]+token == 'bc':\n",
    "                    stack = []\n",
    "                elif stack[-1]+token == 'ac':\n",
    "                    stack = []\n",
    "                    res +=1\n",
    "                else:\n",
    "                    res += 1 if stack[-1]=='b' else 2\n",
    "                    if token == 'a':\n",
    "                        stack = [token]\n",
    "                    else:\n",
    "                        stack = [token]\n",
    "                        res += 1 if token=='b' else 2\n",
    "            else:\n",
    "                stack = [token] if token != 'c' else []\n",
    "                if token != 'a':\n",
    "                    res += 1 if token == 'b' else 2\n",
    "        if stack:\n",
    "            res += 1 if stack[-1]=='b' else 2\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addMinimum(self, word: str) -> int:\n",
    "\n",
    "        \n",
    "        # scan from left to right remove all 'c' then all 'b' then all 'a'\n",
    "\n",
    "        # wrong due to non remove\n",
    "        # st = []\n",
    "\n",
    "        # ret = 0\n",
    "        # for c in word:\n",
    "        #     if c == 'c':\n",
    "        #         if not st:\n",
    "        #             ret += 2\n",
    "        #             continue\n",
    "        #         else:\n",
    "        #             pre = st.pop()\n",
    "        #             if pre == 'b' and st and st[-1] == 'a':\n",
    "        #                 st.pop()\n",
    "        #                 continue\n",
    "\n",
    "        #             ret += 1\n",
    "        #             continue\n",
    "        #     else:\n",
    "        #         st.append(c)\n",
    "\n",
    "        # print(ret)\n",
    "        # print(st)\n",
    "        # rw = ''.join(st)\n",
    "        # rw_n = len(rw)\n",
    "\n",
    "        # rw = rw.replace('ab', '')\n",
    "        # print(rw)\n",
    "        # ret += (rw_n - len(rw)) // 2\n",
    "\n",
    "        # ret += len(rw) * 2\n",
    "\n",
    "        # return ret\n",
    "\n",
    "        ret = 0\n",
    "        idx = 0\n",
    "        n = len(word)\n",
    "        while idx < n:\n",
    "            \n",
    "            if word[idx: idx + 3] == 'abc':\n",
    "                idx += 3\n",
    "                continue\n",
    "\n",
    "            if idx == n - 1:\n",
    "                ret += 2\n",
    "                idx += 1\n",
    "                continue\n",
    "\n",
    "            if word[idx: idx + 2] in ('ab', 'bc', 'ac'):\n",
    "                ret += 1\n",
    "                idx += 2\n",
    "                continue\n",
    "            \n",
    "            ret += 2\n",
    "            idx += 1\n",
    "        \n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addMinimum(self, word: str) -> int:\n",
    "        t = 1 + sum(x >= y for x, y in pairwise(word))\n",
    "        return t * 3 - len(word)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addMinimum(self, word: str) -> int:\n",
    "\n",
    "        t = 1\n",
    "\n",
    "        for i in range(1, len(word)):\n",
    "            if word[i] <= word[i - 1]:\n",
    "                t+= 1\n",
    "        return 3* t - len(word)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addMinimum(self, word: str) -> int:\n",
    "        t=1+sum(x>=y for x,y in pairwise(word))\n",
    "        return t*3-len(word)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addMinimum(self, word: str) -> int:\n",
    "        dic = {\"a\": 0, \"b\": 1, \"c\": 2}\n",
    "        return dic[word[0]] + sum((dic[word[i + 1]] - dic[word[i]] - 1) % 3 for i in range(len(word) - 1)) + (2 - dic[word[-1]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addMinimum(self, word: str) -> int:\n",
    "        n = len(word)\n",
    "        if (n == 1):\n",
    "            return 2\n",
    "        left = 0\n",
    "        right = 1\n",
    "        ans = 0\n",
    "        while (left < n):\n",
    "            while (right < n and word[right-1] < word[right]):\n",
    "                right += 1\n",
    "            ans += 3 + left - right\n",
    "            left = right\n",
    "            right += 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addMinimum(self, word: str) -> int:\n",
    "        ans = 0\n",
    "        n = len(word)\n",
    "        ans += ord(word[0])-ord(word[n-1])+2\n",
    "        for x,y in pairwise(word):\n",
    "            ans += (ord(y)-ord(x)+2)%3\n",
    "        return ans\n",
    "        # iters = 1+sum(x>=y for x,y in pairwise(word))\n",
    "        # return 3*iters - len(word)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addMinimum(self, word: str) -> int:\n",
    "        '''\n",
    "        先计算出最终有n个'abc' -> 3 * n - len(word)就是结果\n",
    "\n",
    "        如何计算最终有多少个'abc':\n",
    "        遍历word[i], word[i+1]，每次出现一次 word[i+1] <= word[i]，就一定会诞生一个'abc'\n",
    "        '''\n",
    "\n",
    "        cnt = 1\n",
    "\n",
    "        for i in range(len(word) - 1):\n",
    "            if word[i+1] <= word[i]:\n",
    "                cnt += 1\n",
    "\n",
    "        return cnt * 3 - len(word)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''class Solution:\n",
    "    def addMinimum(self, s: str) -> int:\n",
    "        t = 1 + sum(x >= y for x, y in pairwise(s))\n",
    "        return t * 3 - len(s)'''\n",
    "class Solution:\n",
    "    def addMinimum(self, s: str) -> int:\n",
    "        ans = ord(s[0]) - ord(s[-1]) + 2\n",
    "        for x, y in pairwise(map(ord, s)):\n",
    "            ans += (y - x + 2) % 3\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addMinimum(self, word: str) -> int:\n",
    "        n = len(word)\n",
    "        cnt = 0\n",
    "        stack = []\n",
    "        for i in range(n):\n",
    "            if word[i] == \"a\":\n",
    "                if stack:\n",
    "                    if stack[-1] == \"b\":\n",
    "                        cnt += 1\n",
    "                    if stack[-1] == \"a\":\n",
    "                        cnt += 2\n",
    "                stack = [\"a\"]\n",
    "            if word[i] == \"b\":\n",
    "                if not stack:\n",
    "                    stack = [\"a\", \"b\"]\n",
    "                    cnt += 1\n",
    "                elif stack[-1] == \"b\":\n",
    "                    cnt += 2\n",
    "                else:\n",
    "                    stack.append(\"b\")\n",
    "            elif word[i] == \"c\":\n",
    "                if not stack:\n",
    "                    cnt += 2\n",
    "                elif stack[-1] == \"a\":\n",
    "                    cnt += 1\n",
    "                stack = []\n",
    "        return cnt + (3 - len(stack)) % 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addMinimum(self, word: str) -> int:\n",
    "        substring_to_remove = \"abc\"\n",
    "        count1 = word.count(substring_to_remove)\n",
    "        substring_to_remove = \"ab\"\n",
    "        count2 = word.count(substring_to_remove)\n",
    "        substring_to_remove = \"bc\"\n",
    "        count3 = word.count(substring_to_remove)\n",
    "        substring_to_remove = \"ac\"\n",
    "        count4 = word.count(substring_to_remove)\n",
    "        return count3+count2+count4 - 2*count1+(len(word) - 3*count1 - 2*(count2 + count3 +count4- 2*count1))*2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addMinimum(self, s: str) -> int:\n",
    "        ans = ord(s[0]) - ord(s[-1]) + 2\n",
    "        for x,y in pairwise(map(ord,s)):\n",
    "            ans += (y - x + 2) % 3\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addMinimum(self, word: str) -> int:\n",
    "        letterList = [\"a\", \"b\", \"c\"]\n",
    "        i = 0\n",
    "        ret = 0\n",
    "        while i < len(word):\n",
    "            expectLetter = letterList[i%3]\n",
    "            if word[i] != expectLetter:\n",
    "                word = word[:i] + expectLetter + word[i:]\n",
    "                ret += 1\n",
    "            i += 1\n",
    "\n",
    "        return ret + (3 - i%3)%3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addMinimum(self, word: str) -> int:\n",
    "        word += \"AA\"\n",
    "        i = 0\n",
    "        ans = 0\n",
    "        while i < len(word) - 2:\n",
    "            if word[i] == \"a\" and word[i + 1] == \"b\" and word[i + 2] == \"c\":\n",
    "                i += 3\n",
    "            elif word[i] == \"a\" and word[i + 1] == \"b\":\n",
    "                ans += 1\n",
    "                i += 2\n",
    "            elif word[i] == \"a\" and word[i + 1] == \"c\":\n",
    "                ans += 1\n",
    "                i += 2\n",
    "            elif word[i] == \"a\":\n",
    "                ans += 2\n",
    "                i += 1\n",
    "            elif word[i] == \"b\" and word[i + 1] == \"c\":\n",
    "                ans += 1\n",
    "                i += 2\n",
    "            elif word[i] == \"b\":\n",
    "                ans += 2\n",
    "                i += 1\n",
    "            else:\n",
    "                ans += 2\n",
    "                i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addMinimum(self, s: str) -> int:\n",
    "        ans = ord(s[0]) - ord(s[-1]) + 2\n",
    "        for x, y in pairwise(map(ord, s)):\n",
    "            ans += (y - x + 2) % 3\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addMinimum(self, word: str) -> int:\n",
    "        index=1\n",
    "        n=len(word)\n",
    "        for i in range(1,n):\n",
    "            if ord(word[i])<=ord(word[i-1]):\n",
    "                index+=1\n",
    "        return 3*index-n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addMinimum(self, word: str) -> int:\n",
    "        res = 0\n",
    "        idx = 0\n",
    "        while idx < len(word):\n",
    "            if word[idx] == 'a':\n",
    "                tmp_s = word[idx:idx+3]\n",
    "                if tmp_s == 'abc':\n",
    "                    idx += 3\n",
    "                    continue\n",
    "                elif tmp_s[:2] == 'ab' or tmp_s[:2] == 'ac' :\n",
    "                    idx += 2\n",
    "                    res += 1\n",
    "                    continue\n",
    "                else:\n",
    "                    idx += 1\n",
    "                    res += 2\n",
    "                    continue\n",
    "            elif word[idx] == 'b':\n",
    "                tmp_s = word[idx:idx+2]\n",
    "                if tmp_s == 'bc':\n",
    "                    res += 1\n",
    "                    idx += 2\n",
    "                    continue\n",
    "                else:\n",
    "                    res += 2\n",
    "                    idx += 1\n",
    "                    continue\n",
    "            else:\n",
    "                res += 2\n",
    "                idx += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addMinimum(self, word: str) -> int:\n",
    "        word = word.replace('abc', ' ')\n",
    "        word = word.replace('ab', '1')\n",
    "        word = word.replace('bc', '1')\n",
    "        word = word.replace('ac','1')\n",
    "        word = word.replace('a', '2')\n",
    "        word = word.replace('b', '2')\n",
    "        word = word.replace('c', '2')\n",
    "        return word.count('1') + word.count('2')*2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addMinimum(self, word: str) -> int:\n",
    "        target = 'abc'\n",
    "        p1 = 0\n",
    "        result = 0\n",
    "        while p1 < len(word):\n",
    "            p2 = p1\n",
    "            t = 0\n",
    "            while t < len(target):\n",
    "                if p2 == len(word) :\n",
    "                    return result +(len(target) - t)\n",
    "                    pass\n",
    "                if word[p2] != target[t]:\n",
    "                    t += 1\n",
    "                    result += 1\n",
    "                    pass\n",
    "                else:\n",
    "                    t += 1\n",
    "                    p2 += 1\n",
    "                    pass\n",
    "                pass\n",
    "            p1 = p2\n",
    "            pass\n",
    "        return result\n",
    "        pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addMinimum(self, word: str) -> int:\n",
    "        char = ['a', 'b', 'c']\n",
    "        cur_idx = 0\n",
    "        i = res = 0\n",
    "        while i < len(word):\n",
    "            if word[i] != char[cur_idx]:\n",
    "                res += 1\n",
    "            else:\n",
    "                i += 1\n",
    "            cur_idx = (cur_idx+1) % 3\n",
    "        return res + (3-cur_idx) % 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addMinimum(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        t = 1 + sum(s[i]>=s[i+1] for i in range(n-1))\n",
    "        return t * 3 - n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addMinimum(self, word: str) -> int:\n",
    "        if len(word) == 1:\n",
    "            return 2\n",
    "        mylist = {\"a\":0,\"b\":1,\"c\":2}\n",
    "        ans = 0\n",
    "        for i in range(len(word)):\n",
    "            if i == 0:\n",
    "                if word[i] != \"a\":\n",
    "                    ans += mylist[word[i]]\n",
    "                else :\n",
    "                    continue\n",
    "            else :\n",
    "                if (mylist[word[i-1]] + 1) % 3 == mylist[word[i]]:\n",
    "                    continue\n",
    "                elif word[i] == word[i-1]:\n",
    "                    ans += 2\n",
    "                else :\n",
    "                    ans += 1\n",
    "        if word[-1] != \"c\":\n",
    "            ans += 2 - mylist[word[-1]]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addMinimum(self, word: str) -> int:\n",
    "        pre = ''\n",
    "        result = 0\n",
    "        for c in word:\n",
    "            if(c == 'a'):\n",
    "                if(pre == ''):\n",
    "                    pre = 'a'\n",
    "                elif(pre == 'a'):\n",
    "                    result += 2\n",
    "                    pre = 'a'\n",
    "                elif(pre == 'ab'):\n",
    "                    result += 1\n",
    "                    pre = 'a'\n",
    "                else:\n",
    "                    result += 2\n",
    "                    pre = 'a'\n",
    "                    \n",
    "            elif(c == 'b'):\n",
    "                if(pre == ''):\n",
    "                    pre = 'b'\n",
    "                elif(pre == 'a'):\n",
    "                    pre = 'ab'\n",
    "                elif(pre == 'ab'):\n",
    "                    result += 1\n",
    "                    pre = 'b'\n",
    "                else:\n",
    "                    result += 2\n",
    "                    pre = 'b'\n",
    "            else:\n",
    "                if(pre == ''):\n",
    "                    result += 2\n",
    "                    pre = ''\n",
    "                elif(pre == 'a'):\n",
    "                    result += 1\n",
    "                    pre = ''\n",
    "                elif(pre == 'ab'):\n",
    "                    pre = ''\n",
    "                else:\n",
    "                    result += 1\n",
    "                    pre = ''\n",
    "        if(len(pre) > 0):\n",
    "            result += 3 - len(pre)\n",
    "        return result\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addMinimum(self, word: str) -> int:\n",
    "        count=0\n",
    "        ans=0\n",
    "        for i in range(len(word)):\n",
    "            if count==0:\n",
    "                if word[i]=='a':\n",
    "                    count+=1\n",
    "                elif word[i]=='b':\n",
    "                    ans+=1\n",
    "                    count+=2\n",
    "                else:\n",
    "                    ans+=2\n",
    "            elif count==1:\n",
    "                if word[i]=='a':\n",
    "                    ans+=2\n",
    "                    \n",
    "                elif word[i]=='b':\n",
    "                    count+=1\n",
    "                else:\n",
    "                    ans+=1\n",
    "                    count=0\n",
    "            else:\n",
    "                if word[i]=='a':\n",
    "                    ans+=1\n",
    "                    count=1\n",
    "                elif word[i]=='b':\n",
    "                    ans+=2\n",
    "                    count=2\n",
    "                else:\n",
    "                    count=0\n",
    "\n",
    "        if count==1: \n",
    "            ans+=2\n",
    "        if count==2: \n",
    "            ans+=1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addMinimum(self, word: str) -> int:\n",
    "        former = -1\n",
    "        cnt = 0\n",
    "        for c in word:\n",
    "            cur = ord(c)-ord('a')\n",
    "            if cur > former:\n",
    "                cnt += cur-former-1\n",
    "            else:\n",
    "                cnt += cur+2-former\n",
    "            former = cur\n",
    "            # print(c, cnt)\n",
    "        cnt += 2-former\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addMinimum(self, word: str) -> int:\n",
    "        word = word.replace('abc', ' ')\n",
    "        word = word.replace('ab', '1')\n",
    "        word = word.replace('bc', '1')\n",
    "        word = word.replace('ac','1')\n",
    "        word = word.replace('a', '2')\n",
    "        word = word.replace('b', '2')\n",
    "        word = word.replace('c', '2')\n",
    "        return word.count('1') + word.count('2')*2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addMinimum(self, word: str) -> int:\n",
    "        #abc; a\n",
    "        n = len(word)\n",
    "        stack = ''\n",
    "        pay = {'abc','ab','a','b','bc'}\n",
    "        ans = 0\n",
    "        for x in word:\n",
    "            stack += x\n",
    "            if stack not in pay and x != 'c':\n",
    "                ans += 4 - len(stack)\n",
    "                stack = x\n",
    "            if x == 'c':\n",
    "                ans += 3 - len(stack)\n",
    "                stack = ''\n",
    "        return ans + (3 - len(stack))%3\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addMinimum(self, word: str) -> int:\n",
    "        alpha_dict = dict()\n",
    "        word = list(word)\n",
    "        index = 0\n",
    "        cnt = 0\n",
    "        while index < len(word):\n",
    "            if word[index] == 'a':\n",
    "                if index+1 == len(word):\n",
    "                    word.append('b')\n",
    "                    word.append('c')\n",
    "                    cnt += 2\n",
    "                    return cnt\n",
    "                if word[index+1] == 'a':\n",
    "                    cnt += 2\n",
    "                    word.insert(index+1,'c')\n",
    "                    word.insert(index+1,'b')\n",
    "                    index += 2\n",
    "                    continue\n",
    "                if word[index+1] == 'b':\n",
    "                    index += 1\n",
    "                    continue\n",
    "                if word[index+1] == 'c':\n",
    "                    cnt += 1\n",
    "                    word.insert(index+1,'b')\n",
    "                    index += 2\n",
    "                    continue\n",
    "            if word[index] == 'b':\n",
    "                if index - 1 == -1 or word[index-1] != 'a':\n",
    "                    cnt += 1\n",
    "                    word.insert(index,'a')\n",
    "                    index += 1\n",
    "                    continue\n",
    "                if index+1 == len(word):\n",
    "                    word.append('c')\n",
    "                    cnt += 1\n",
    "                    return cnt\n",
    "                if word[index+1] != 'c':\n",
    "                    cnt += 1\n",
    "                    word.insert(index+1,'c')\n",
    "                    index += 1\n",
    "                    continue\n",
    "                index += 1\n",
    "            else:\n",
    "                if index - 1 == -1 or word[index-1] != 'b':\n",
    "                    cnt += 2\n",
    "                    word.insert(index,'b')\n",
    "                    word.insert(index,'a')\n",
    "                    index += 1\n",
    "                    continue\n",
    "                index += 1\n",
    "        return cnt\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addMinimum(self, word: str) -> int:\n",
    "        if len(word) == 1:\n",
    "            return 2\n",
    "        mylist = {\"a\":0,\"b\":1,\"c\":2}\n",
    "        ans = 0\n",
    "        for i in range(len(word)):\n",
    "            if i == 0:\n",
    "                if word[i] != \"a\":\n",
    "                    ans += mylist[word[i]]\n",
    "                else :\n",
    "                    continue\n",
    "            else :\n",
    "                if (mylist[word[i-1]] + 1) % 3 == mylist[word[i]]:\n",
    "                    continue\n",
    "                elif word[i] == word[i-1]:\n",
    "                    ans += 2\n",
    "                else :\n",
    "                    ans += 1\n",
    "        if word[-1] != \"c\":\n",
    "            ans += 2 - mylist[word[-1]]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addMinimum(self, word: str) -> int:\n",
    "\n",
    "        word = word.replace('abc', ' ')\n",
    "        word = word.replace('ab', '1')\n",
    "        word = word.replace('bc', '1')\n",
    "        word = word.replace('ac','1')\n",
    "        word = word.replace('a', '2')\n",
    "        word = word.replace('b', '2')\n",
    "        word = word.replace('c', '2')\n",
    "        return word.count('1') + word.count('2')*2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addMinimum(self, word: str) -> int:\n",
    "        res = 0\n",
    "        count = 0\n",
    "        for i,c in enumerate(word):\n",
    "            if c == 'a':\n",
    "                res += (3-count)%3\n",
    "                count = 1\n",
    "            elif c == 'b':\n",
    "                if count == 0:\n",
    "                    res += 1\n",
    "                elif count == 2:\n",
    "                    res += 2\n",
    "                count = 2\n",
    "            else:\n",
    "                if count == 0:\n",
    "                    res += 2\n",
    "                elif count == 1:\n",
    "                    res += 1\n",
    "                count = 0\n",
    "        return res + (3-count)%3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addMinimum(self, word: str) -> int:\n",
    "        word=word.replace('abc','*')\n",
    "        n3 = word.count('*')\n",
    "        word=word.replace('ac',',')\n",
    "        word=word.replace('ab',',')\n",
    "        word=word.replace('bc',',')\n",
    "        n2 = word.count(',')\n",
    "        word=word.replace(',','')\n",
    "        word=word.replace('*','')\n",
    "        n1=len(word)\n",
    "        return n1*2+n2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addMinimum(self, word: str) -> int:\n",
    "        ans = ord(word[0]) - ord('a')\n",
    "        for i in range(1, len(word)):\n",
    "            ans += ((ord(word[i]) - ord(word[i - 1])) - 1 + 3) % 3\n",
    "        return ans + ord('c') - ord(word[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addMinimum(self, word: str) -> int:\n",
    "        '''\n",
    "        计算至少需要N个'abc' -> return 3*N - len(word)\n",
    "        '''\n",
    "        # 计算至少需要N个'abc'\n",
    "        N = 1\n",
    "        for i in range(1, len(word)):\n",
    "            N += word[i] <= word[i - 1]\n",
    "\n",
    "        return 3 * N - len(word)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addMinimum(self, word: str) -> int:\n",
    "        n = len(word)\n",
    "        groups = 1\n",
    "        for i in range(1, n):\n",
    "            if word[i] <= word[i-1]:\n",
    "                groups += 1\n",
    "        return groups * 3 - n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addMinimum(self, w: str) -> int:\n",
    "        ans=0\n",
    "        c=0\n",
    "        for i in w:\n",
    "            # print(i,c,chr(ord('a')+c))\n",
    "            while i!=chr(ord('a')+c):\n",
    "                ans+=1\n",
    "                c=(c+1)%3\n",
    "            c=(c+1)%3\n",
    "        if c!=0:\n",
    "            ans+=3-c\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addMinimum(self, word: str) -> int:\n",
    "        n = len(word)\n",
    "        s = 1\n",
    "        for i in range(1, n):\n",
    "            if word[i] <= word[i - 1]:\n",
    "                s += 1\n",
    "        return 3 * s - n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addMinimum(self, word: str) -> int:\n",
    "        ans = 0\n",
    "        n = len(word)\n",
    "        ans += ord(word[0]) - ord('a')\n",
    "        ans += ord('c') - ord(word[-1])\n",
    "        if n == 1: return ans\n",
    "        else:\n",
    "            for i in range(1, n):\n",
    "                ans += (ord(word[i]) - ord(word[i-1]) + 2) % 3\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addMinimum(self, word: str) -> int:\n",
    "        if   word     == \"\"   : return 0\n",
    "        elif word[:3] == \"abc\": return self.addMinimum(word[3:])\n",
    "        elif word[:2] in (\"ab\", \"ac\", \"bc\"): return 1 + self.addMinimum(word[2:])\n",
    "        elif word[:1] in (\"a\",  \"b\",  \"c\" ): return 2 + self.addMinimum(word[1:])    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addMinimum(self, word: str) -> int:\n",
    "        # char = ['a', 'b', 'c']\n",
    "        # cur_idx = 0\n",
    "        # i = res = 0\n",
    "        # while i < len(word):\n",
    "        #     if word[i] != char[cur_idx]:\n",
    "        #         res += 1\n",
    "        #     else:\n",
    "        #         i += 1\n",
    "        #     cur_idx = (cur_idx+1) % 3\n",
    "        # return res + (3-cur_idx) % 3\n",
    "\n",
    "        # -------------------------------\n",
    "        # x, y need to insert y - x - 1 ch, which can be converted to (y - x + 2) % 3\n",
    "        res = ord(word[0]) - ord(word[-1]) + 2\n",
    "        for x, y in pairwise(word):\n",
    "            res += (ord(y)-ord(x)+2) % 3\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addMinimum(self, word: str) -> int:\n",
    "        return (1+sum(x>=y for x,y in pairwise(word)))*3 -len(word)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addMinimum(self, word: str) -> int:\n",
    "        res, p = {'a':2, 'b': 1, 'c': 0}[word[-1]], 0\n",
    "        for target in itertools.cycle('abc'):\n",
    "            if word[p] != target: res += 1\n",
    "            else: p += 1\n",
    "            if p==len(word): return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addMinimum(self, word: str) -> int:\n",
    "        cur = 0\n",
    "        cur_abc = 0\n",
    "        n = len(word)\n",
    "        ans = 0\n",
    "        while cur < n:\n",
    "            if word[cur] == chr(cur_abc + 97):\n",
    "                cur += 1\n",
    "            else:\n",
    "                ans += 1\n",
    "            cur_abc = (cur_abc + 1) % 3\n",
    "        return ans + (3 - cur_abc) % 3\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addMinimum(self, word: str) -> int:\n",
    "        res = 0\n",
    "        \n",
    "        S = {\n",
    "            'a': {'a': 2, 'b': 0, 'c': 1},\n",
    "            'b': {'a': 1, 'b': 2, 'c': 0},\n",
    "            'c': {'a': 0, 'b': 1, 'c': 2}\n",
    "        }\n",
    "        \n",
    "        for x, y in itertools.pairwise(word):\n",
    "            res += S[x][y]\n",
    "    \n",
    "        if word[0] == 'b':\n",
    "            res += 1\n",
    "        elif word[0] == 'c':\n",
    "            res += 2\n",
    "        \n",
    "        if word[-1] == 'a':\n",
    "            res += 2\n",
    "        elif word[-1] == 'b':\n",
    "            res += 1\n",
    "        \n",
    "        return res\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addMinimum(self, word: str) -> int:\n",
    "        ans = 0\n",
    "        tmp = '' #表示最终需要多少对abc\n",
    "        for index,w in enumerate(word):\n",
    "            # ans记录给w前面补多少个数字\n",
    "            if tmp and ord(w)==ord(tmp):#当前出现的字母不是记录的下一个\n",
    "                ans +=2 # 当前位和上一位相等，需要加上2\n",
    "                tmp = w\n",
    "            elif tmp and ord(w)-ord(tmp)==2: # a c \n",
    "                ans +=1\n",
    "                tmp = w\n",
    "            elif tmp and ord(w)-ord(tmp)==1: # a b 和b c\n",
    "                tmp = w\n",
    "            elif tmp and ord(w)-ord(tmp)==-2: # c a \n",
    "                tmp = w\n",
    "            elif tmp and ord(w)-ord(tmp)==-1: # b a 和c b\n",
    "                ans +=1\n",
    "                tmp = w\n",
    "            else:\n",
    "                tmp = w #记录上一个\n",
    "                if tmp=='b':\n",
    "                    ans +=1\n",
    "                elif tmp=='c':\n",
    "                    ans+=2\n",
    "                else:\n",
    "                    pass\n",
    "        if tmp=='a':\n",
    "            ans +=2\n",
    "        elif tmp=='b':\n",
    "            ans +=1\n",
    "        else:\n",
    "            pass\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addMinimum(self, word: str) -> int:\n",
    "        pre = ''\n",
    "        result = 0\n",
    "        for c in word:\n",
    "            if(c == 'a'):\n",
    "                if(pre == ''):\n",
    "                    pre = 'a'\n",
    "                elif(pre == 'a'):\n",
    "                    result += 2\n",
    "                    pre = 'a'\n",
    "                elif(pre == 'ab'):\n",
    "                    result += 1\n",
    "                    pre = 'a'\n",
    "                else:\n",
    "                    result += 2\n",
    "                    pre = 'a'\n",
    "            elif(c == 'b'):\n",
    "                if(pre == ''):\n",
    "                    pre = 'b'\n",
    "                elif(pre == 'a'):\n",
    "                    pre = 'ab'\n",
    "                elif(pre == 'ab'):\n",
    "                    result += 1\n",
    "                    pre = 'b'\n",
    "                else:\n",
    "                    result += 2\n",
    "                    pre = 'b'\n",
    "            else:\n",
    "                if(pre == ''):\n",
    "                    result += 2\n",
    "                    pre = ''\n",
    "                elif(pre == 'a'):\n",
    "                    result += 1\n",
    "                    pre = ''\n",
    "                elif(pre == 'ab'):\n",
    "                    pre = ''\n",
    "                else:\n",
    "                    result += 1\n",
    "                    pre = ''\n",
    "        if(len(pre) > 0):\n",
    "            result += 3 - len(pre)\n",
    "        return result\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addMinimum(self, word: str) -> int:\n",
    "        ans = 0\n",
    "        st = ''\n",
    "        for c in word:\n",
    "            if c == 'a':\n",
    "                if not st:\n",
    "                    st = c\n",
    "                elif st == 'a':\n",
    "                    ans += 2\n",
    "                elif st == 'b':\n",
    "                    st = c\n",
    "                    ans += 1\n",
    "            elif c == 'b':\n",
    "                if not st:\n",
    "                    st = c\n",
    "                    ans += 1\n",
    "                elif st == 'a':\n",
    "                    st = c\n",
    "                elif st == 'b':\n",
    "                    ans += 2\n",
    "            else:\n",
    "                if not st:\n",
    "                    ans += 2\n",
    "                elif st == 'b':\n",
    "                    st = ''\n",
    "                elif st == 'a':\n",
    "                    st = ''\n",
    "                    ans += 1\n",
    "        if st == 'a': ans += 2\n",
    "        elif st == 'b': ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addMinimum(self, word: str) -> int:\n",
    "        ans = 0\n",
    "        word = word.split('abc')\n",
    "        for w in word:\n",
    "            pre = ''\n",
    "            for c in w:\n",
    "                if pre == '':\n",
    "                    pre = c\n",
    "                    continue\n",
    "                if pre == 'a':\n",
    "                    if c in ['b', 'c']:\n",
    "                        ans += 1\n",
    "                    else:\n",
    "                        ans += 2\n",
    "                    pre = '' if c != 'a' else c\n",
    "                elif pre == 'b':\n",
    "                    if c == 'c':\n",
    "                        ans += 1\n",
    "                    else:\n",
    "                        ans += 2\n",
    "                    pre = c if c != 'c' else ''\n",
    "                else:\n",
    "                    ans += 2\n",
    "                    pre = c\n",
    "            if pre != '':\n",
    "                ans += 2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addMinimum(self, word: str) -> int:\n",
    "        alpha_dict = dict()\n",
    "        word = list(word)\n",
    "        index = 0\n",
    "        cnt = 0\n",
    "        while index < len(word):\n",
    "            print(word)\n",
    "            print(index)\n",
    "            print(cnt)\n",
    "            if word[index] == 'a':\n",
    "                if index+1 == len(word):\n",
    "                    word.append('b')\n",
    "                    word.append('c')\n",
    "                    cnt += 2\n",
    "                    return cnt\n",
    "                if word[index+1] == 'a':\n",
    "                    cnt += 2\n",
    "                    word.insert(index+1,'c')\n",
    "                    word.insert(index+1,'b')\n",
    "                    index += 2\n",
    "                    continue\n",
    "                if word[index+1] == 'b':\n",
    "                    index += 1\n",
    "                    continue\n",
    "                if word[index+1] == 'c':\n",
    "                    cnt += 1\n",
    "                    word.insert(index+1,'b')\n",
    "                    index += 2\n",
    "                    continue\n",
    "            if word[index] == 'b':\n",
    "                if index - 1 == -1 or word[index-1] != 'a':\n",
    "                    cnt += 1\n",
    "                    word.insert(index,'a')\n",
    "                    index += 1\n",
    "                    continue\n",
    "                if index+1 == len(word):\n",
    "                    word.append('c')\n",
    "                    cnt += 1\n",
    "                    return cnt\n",
    "                if word[index+1] != 'c':\n",
    "                    cnt += 1\n",
    "                    word.insert(index+1,'c')\n",
    "                    index += 1\n",
    "                    continue\n",
    "                index += 1\n",
    "            else:\n",
    "                if index - 1 == -1 or word[index-1] != 'b':\n",
    "                    cnt += 2\n",
    "                    word.insert(index,'b')\n",
    "                    word.insert(index,'a')\n",
    "                    index += 1\n",
    "                    continue\n",
    "                index += 1\n",
    "        return cnt\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addMinimum(self, word: str) -> int:\n",
    "        ans=0\n",
    "        i=0\n",
    "        n=len(word)\n",
    "        while i<n:\n",
    "            if word[i]=='a':\n",
    "                if i<n-1 and word[i+1]=='b':\n",
    "                    if i<n-2 and word[i+2]=='c':\n",
    "                        i+=3\n",
    "                    else:\n",
    "                        ans+=1\n",
    "                        i+=2\n",
    "                elif i<n-1 and word[i+1]=='c':\n",
    "                    ans+=1\n",
    "                    i+=2\n",
    "                else:\n",
    "                    ans+=2\n",
    "                    i+=1\n",
    "            elif word[i]=='b':\n",
    "                if i<n-1 and word[i+1]=='c':\n",
    "                    ans+=1\n",
    "                    i+=2\n",
    "                else:\n",
    "                    ans+=2\n",
    "                    i+=1\n",
    "            else:\n",
    "                ans+=2\n",
    "                i+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addMinimum(self, word: str) -> int:\n",
    "        t=1+sum(x>=y for x,y in pairwise(word))\n",
    "        return 3*t-len(word)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addMinimum(self, word: str) -> int:\n",
    "        n = len(word)\n",
    "        cnt = 0\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            if word[i] == \"a\":\n",
    "                if i + 1 < n and word[i + 1] == \"b\":\n",
    "                    if i + 2 < n and word[i + 2] == \"c\":\n",
    "                        i += 3\n",
    "                    else:\n",
    "                        cnt += 1\n",
    "                        i += 2\n",
    "                elif i + 1 < n and word[i + 1] == \"c\":\n",
    "                    i += 2\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    i += 1\n",
    "                    cnt += 2\n",
    "            elif word[i] == \"b\":\n",
    "                if i + 1 < n and word[i + 1] == \"c\":\n",
    "                    i += 2\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    i += 1\n",
    "                    cnt += 2\n",
    "            else:\n",
    "                i += 1\n",
    "                cnt += 2\n",
    "        return cnt\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addMinimum(self, s: str) -> int:\n",
    "        ans = ord(s[0]) - ord(s[-1]) + 2\n",
    "        for x, y in pairwise(map(ord, s)):\n",
    "            ans += (y - x + 2) % 3\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addMinimum(self, word: str) -> int:\n",
    "        p=0\n",
    "        ans=0\n",
    "        mp={'a':0,'b':1,'c':2}\n",
    "        word+='a'\n",
    "        for ch in word:\n",
    "            if mp[ch]>p:\n",
    "                ans+=mp[ch]-p\n",
    "            elif mp[ch]<p:\n",
    "                ans+=3+mp[ch]-p\n",
    "            p=mp[ch]+1\n",
    "            p%=3\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addMinimum(self, word: str) -> int:\n",
    "        ret = 1\n",
    "        for i in range(1, len(word)):\n",
    "            ret += word[i-1] >= word[i]\n",
    "        return ret * 3 - len(word)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addMinimum(self, word: str) -> int:\n",
    "        n = len(word)\n",
    "        count = i = k = 0\n",
    "        plan = \"abc\"\n",
    "        while i<n:\n",
    "            while word[i] != plan[k%3]:\n",
    "                count += 1\n",
    "                k+=1\n",
    "            i += 1\n",
    "            k += 1\n",
    "        if word[-1] == \"a\":\n",
    "            count += 2\n",
    "        elif word[-1] == \"b\":\n",
    "            count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addMinimum(self, word: str) -> int:\n",
    "        result = 0\n",
    "        p1 = 0\n",
    "        target = 'abc'\n",
    "        while p1 < len(word):\n",
    "            p2 = p1\n",
    "            t = 0\n",
    "            while t < len(target) and p2 < len(word):\n",
    "                if target[t] == word[p2]:\n",
    "                    t += 1\n",
    "                    p2 += 1\n",
    "                    pass\n",
    "                else:\n",
    "                    t += 1\n",
    "                    result += 1\n",
    "                    pass\n",
    "            if t == len(target):\n",
    "                p1 = p2\n",
    "                pass\n",
    "            else:\n",
    "                return result + (len(target) - t)\n",
    "                pass\n",
    "\n",
    "            pass\n",
    "        return result\n",
    "        pass\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addMinimum(self, word: str) -> int:\n",
    "        ans=0\n",
    "        temp=2\n",
    "        n=len(word)\n",
    "        for i in range(n-1):\n",
    "            if ord(word[i+1])-ord(word[i])==1:\n",
    "                temp-=1\n",
    "            elif ord(word[i+1])-ord(word[i])==2:\n",
    "                i+=1\n",
    "                ans+=1\n",
    "                temp=0\n",
    "            else:\n",
    "                ans+=temp\n",
    "                temp=2\n",
    "        return ans+temp\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
